{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基数排序（英语：Radix sort）\n",
    "\n",
    "    是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    所以基数排序的原理就是，先排元素的最后一位，再排倒数第二位，直到所有位数都排完。这里并不能先排第一位，那样最后依然是无序。\n",
    "    \n",
    "    基数排序不仅仅只能排正整数，只要通过调整元素放入桶数组的方式就可以排序字符串，浮点数等"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def radix_sort(nums):\n",
    "    i = 0\n",
    "    max_num = max(nums)\n",
    "    \n",
    "    j = len(str(max_num))\n",
    "    \n",
    "    while i < j:\n",
    "        bucket_list = [[] for _ in range(10)]\n",
    "        for x in nums:\n",
    "            bucket_list[int(x / 10**i) % 10].append(x)           # 由于桶已经排好序，所以分桶时，其实每个桶已经有序了\n",
    "        print(bucket_list)\n",
    "        nums.clear()\n",
    "        for x in bucket_list:\n",
    "            for y in x:\n",
    "                nums.append(y)\n",
    "        i += 1\n",
    "        print(nums)\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [1], [], [23, 3453], [334, 4, 23424], [5, 345, 345345, 45], [], [67, 7], [78], [99]]\n",
      "[1, 23, 3453, 334, 4, 23424, 5, 345, 345345, 45, 67, 7, 78, 99]\n",
      "[[1, 4, 5, 7], [], [23, 23424], [334], [345, 345345, 45], [3453], [67], [78], [], [99]]\n",
      "[1, 4, 5, 7, 23, 23424, 334, 345, 345345, 45, 3453, 67, 78, 99]\n",
      "[[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 345345], [23424, 3453], [], [], [], [], []]\n",
      "[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 345345, 23424, 3453]\n",
      "[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345], [], [], [23424, 3453], [], [345345], [], [], [], []]\n",
      "[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 23424, 3453, 345345]\n",
      "[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453], [], [23424], [], [345345], [], [], [], [], []]\n",
      "[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]\n",
      "[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424], [], [], [345345], [], [], [], [], [], []]\n",
      "[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "radix_sort(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
